Side Channel Information Set Decoding: Plaintext Recovery from the "Classic McEliece" Hardware Reference Implementation

This paper presents an attack based on side-channel information and information set decoding on the Niederreiter cryptosystem and an evaluation of the practicality of the attack using a physical side channel. First, we describe a basic plaintext-recovery attack on the decryption algorithm of the Niederreiter cryptosystem. Our attack is an adaptation of the timing side-channel plaintext-recovery attack by Shoufan et al. from 2010 on the McEliece cryptosystem using the non-constant time Patterson's algorithm for decoding. We then enhance our attack by utilizing an Information Set Decoding approach to support the basic attack and we introduce column chunking to further significantly reduce the number of required side-channel measurements. Our practical evaluation of the attack targets the FPG A-implementation of the Niederreiter cryptosystem in the NIST submission “Classic McEliece'' with a constant time decoding algorithm and is feasible for all proposed parameters sets of this submission. The attack idea is to distinguish between successful and failed error correction based on the Hamming weight of the decrypted plaintext using the electromagnetic field as side channel. We theoretically estimate that our attack improvements have a significant impact on reducing the number of required side-channel traces. We confirm our findings experimentally and run successful attacks against the “Classic McEliece'' NIST submission parameter sets. E.g., for the 256bit-security parameter set kem/mceliece6960119 we require starting from a basic attack with 6962 traces over a plain ISD approach with 5415 traces down to on average about 606 traces to mount a successful plaintext recovery attack